package com.leetcode;

/**
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 * <p>
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xmlwi1/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class 搜索二维矩阵 {

	/**
	 * 方法 1：暴力破解
	 *
	 * @param matrix
	 * @param target
	 * @return
	 */
	public boolean searchMatrix1(int[][] matrix, int target) {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				if (matrix[i][j] == target) {
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * 方法 2：二分法查找
	 * 这题说了，每行的元素从左到右升序排列。每列的元素从上到下升序排列。如果还是用暴力求解肯定是不明智的，我们可以从矩阵的右上角开始找，
	 * <p>
	 * 1，如果找到就直接返回
	 * <p>
	 * 2，如果没找到就继续查找
	 * <p>
	 * 如果查找的值小于target就往下找
	 * 如果查找的值大于target就往左找。
	 */
	public static boolean searchMatrix2(int[][] matrix, int target) {
		// 行
		int row = 0;
		// 列
		int col = matrix[0].length - 1;

		while (row <= matrix.length - 1 && col >= 0) {
			int val = matrix[row][col];
			if (target == val) {
				return true;
			}
			if (target > val) {
				// 如果查找的值小了，下一步往下找
				row++;
				continue;
			}
			if (target < val) {
				// 如果查找的值大了，下一步往左找
				col--;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		int[][] array = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
		System.out.println(searchMatrix2(array, 5));
	}
}
